package com.star.exam;

public class Num83 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 1, 1, 2, 3};
        //删除链表中的重复元素，保留一个
        ListNode head = new ListNode(arr);
        head = deleteDuplicates1(head);
        // System.out.println(head.toString());
        while (head!=null){
            System.out.println(head.val);
            head=head.next;
        }
    }
 
    public static ListNode deleteDuplicates(ListNode head) {
        //设置一个指向当前元素的指针
        ListNode current = head;
        //当链表为空或者链表中遍历到最后一个元素时，出循环
        while (current != null && current.next != null) {
            //如果找到当前节点和它的下一个结点的值相同，删除掉下一个结点
            if (current.next.val == current.val) {
                current.next = current.next.next;
            } else {
                //如果没有找到，当前节点后移
                current = current.next;
            }
        }
        return head;
    }
 
 
    public static ListNode deleteDuplicates1(ListNode head) {
        //添加一个虚拟的表头结点
        ListNode tempHead = new ListNode(0);
        tempHead.next = head;
        //pre之前虚拟头结点，记录元素的前一个位置，如果要删除当前元素，需要前一个位置的指针
        ListNode cur = head, pre = tempHead;
        //计数器的初始值置为0
        int count = 0;
        //当前链表为空或者遍历到链表的最后一个元素时
        while (cur != null && cur.next != null) {
            //如果当前节点和下一个结点相等，删除下一个结点，计数值加1
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
                count++;
            } else {
                //不相等的情况下需要判断计数值是否为0来确定是否需要删除当前节点
                if (count > 0) {
                    pre.next = cur.next;
                    count = 0;
                } else {
                    pre = cur;
                }
                cur = cur.next;
            }
        }
        //判断尾节点是否需要删除
        if (count > 0) {
            pre.next = cur.next;
        }
        //返回去除虚拟头结点的链表
        return tempHead.next;
    }
 
 
    static class ListNode {
        int val;
        ListNode next;
 
        ListNode(int x) {
            val = x;
        }
 
        public ListNode(int[] arr) {
            if (arr == null || arr.length == 0)
                throw new IllegalArgumentException("arr can to be empty");
            this.val = arr[0];
            ListNode cur = this;
            for (int i = 1; i < arr.length; i++) {
                cur.next = new ListNode(arr[i]);
                cur = cur.next;
            }
        }
 
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            ListNode cur = this;
            while (cur != null) {
                res.append(cur.val + "->");
                cur = cur.next;
            }
            res.append("NULL");
            return res.toString();
        }
    }
}